package kyssion.leetcode.num1_50;

/**
 * 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,2,0]
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: [3,4,-1,1]
 * 输出: 2
 * 示例 3:
 * <p>
 * 输入: [7,8,9,11,12]
 * 输出: 1
 * 说明:
 * <p>
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
 */
public class code41_缺失的第一个正数 {
    public static void main(String[] args) {
        System.out.println(new code41_缺失的第一个正数().firstMissingPositive(
                new int[]{
                        -1,-2,1,3,4
                }
        ));
    }

    /**
     * 这个题目要注意一个点就是 灵活的利用数组长度这个限制
     * 其实我们只要考虑桶排序的思想,将值和数组的键一一对应就可以得到最终的解了
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int maxNum = nums.length;
        for (int a = 0; a < nums.length; a++) {
            int num = nums[a];
            while (num > 0 && num < maxNum && nums[num - 1] != num) {
                nums[a] = nums[num - 1];
                nums[num - 1] = num;
                num = nums[a];
            }
        }
        for (int a = 0; a < nums.length; a++) {
            if (nums[a] != a + 1) {
                return a + 1;
            }
        }
        return nums.length + 1;
    }

    /**
     * 这个使用了一个额外的数组,来优化变量重新赋值的过程
     * @param nums
     * @return
     */
    public int firstMissingPositive2(int[] nums) {
        boolean []b = new boolean[nums.length];
        if(nums.length == 0){
            return 1;
        }
        for(int j = 0; j < nums.length; j++){
            //以为nums.leng+1为界，找到大于0的正整数元素
            if(nums[j] > 0 && nums[j] < nums.length+1){
                b[nums[j]-1] = true;
            }
        }
        int i = 0;
        while(i < nums.length && b[i] == true){
            i++;//i++还原回nums[j]
        }
        return i+1;
    }
}
